package com.shm.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author: shm
 * @dateTime: 2020/9/21 9:27
 * @description: 538. 把二叉搜索树转换为累加树
 * 给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
 *
 *
 *
 * 例如：
 *
 * 输入: 原始二叉搜索树:
 *               5
 *             /   \
 *            2     13
 *
 * 输出: 转换为累加树:
 *              18
 *             /   \
 *           20     13
 */
public class ConvertBST {
    int sum = 0;
    /**
     * @author: shm
     * @dateTime: 2020/9/21 10:20
     * @description: 前言
     * 二叉搜索树是一棵空树，或者是具有下列性质的二叉树：
     *
     * 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
     *
     * 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
     *
     * 它的左、右子树也分别为二叉搜索树。
     *
     * 由这样的性质我们可以发现，二叉搜索树的中序遍历是一个单调递增的有序序列。如果我们反序地中序遍历该二叉搜索树，即可得到一个单调递减的有序序列。
     *
     * 方法一：反序中序遍历
     * 思路及算法
     *
     * 本题中要求我们将每个节点的值修改为原来的节点值加上所有大于它的节点值之和。这样我们只需要反序中序遍历该二叉搜索树，记录过程中的节点值之和，并不断更新当前遍历到的节点的节点值，即可得到题目要求的累加树。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)，其中 nn 是二叉搜索树的节点数。每一个节点恰好被遍历一次。
     *
     * 空间复杂度：O(n)O(n)，为递归过程中栈的开销，平均情况下为 O(\log n)O(logn)，最坏情况下树呈现链状，为 O(n)O(n)。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/convert-bst-to-greater-tree/solution/ba-er-cha-sou-suo-shu-zhuan-huan-wei-lei-jia-sh-14/
     */
    public TreeNode convertBST(TreeNode root) {
        if (root!=null){
            convertBST(root.right);
            sum+=root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }

    /**
     * @author: shm
     * @dateTime: 2020/9/21 10:48
     * @description: 迭代
     * //    作者：lincs
     * //    链接：https://leetcode-cn.com/problems/convert-bst-to-greater-tree/solution/java-iterative-solution-by-lincs-5/
     */
    public TreeNode convertBST_2(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode p = root, prev = null;
        while (!stack.isEmpty() || p != null) {
            while (p != null) {
                stack.push(p);
                p = p.right;
            }
            p = stack.pop();
            // add the greater val
            if (prev != null) {
                p.val += prev.val;
            }
            prev = p;
            p = p.left;
        }
        return root;
    }

}
